package com.gitee.ywj1352.算法.期中考试;

import java.util.*;

public class 第二题 {


    /**
     * 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
     * <p>
     * 满足要求的四元组集合为：
     * [
     * [-1,  0, 0, 1],
     * [-2, -1, 1, 2],
     * [-2,  0, 0, 2]
     * ]
     *
     * @param nums
     * @param target
     * @return
     */
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        boolean[] status = new boolean[nums.length];
        HashSet<String> strings = new HashSet<>();
        ArrayList<List<Integer>> lists = new ArrayList<>();
        helper(nums, status, target, 0, lists, strings, 4, 0, "", new ArrayList<>());
        return lists;
    }


    public static void helper(int[] nums, boolean[] status, int target, int level, List<List<Integer>> res, Set<String> set, int remain, int sum1, String str, List<Integer> r) {
        if (nums.length - level <= remain) {
            return;
        }
        System.out.println(sum1 + ":" + remain + ":" + str);
        if (remain == 0 && sum1 == target) {
            if (!set.contains(str)) {
                res.add(r);
            }
            return;
        }
        ArrayList<Integer> integers1 = new ArrayList<>(r);
        status[level] = false;
        helper(nums, status, target, level + 1, res, set, remain, sum1, str, integers1);
        status[level] = true;
        ArrayList<Integer> integers = new ArrayList<>(r);
        integers.add(nums[level]);
        helper(nums, status, target, level + 1, res, set, remain - 1, sum1 + nums[level], str + "|" + nums[level], integers);
    }

    public static void main(String[] args) {
        /**
         * [1,0,-1,0,-2,2]
         * 0
         */
        int[] arr = {1, 0, -1, 0, -2, 2};

        List<List<Integer>> lists = fourSum(arr, 0);
        for (List<Integer> t :
                lists) {
            System.out.println(t);
        }

    }


}
